public class Solution {
    public boolean exist(char[][] board, String word) {
        if (word == null || "".equals(word) || board == null || board.length == 0 || board[0] == null
                || board[0].length == 0)
            return false;
        int width = board[0].length;
        int height = board.length;
        boolean[][] visited = new boolean[height][width];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (recur(board, word, visited, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    private boolean recur(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)
                || visited[i][j])
            return false;
        if (k + 1 == word.length())
            return true;
        visited[i][j] = true;
        boolean res = recur(board, word, visited, i + 1, j, k + 1) || recur(board, word, visited, i, j + 1, k + 1)
                || recur(board, word, visited, i - 1, j, k + 1) || recur(board, word, visited, i, j - 1, k + 1);
        visited[i][j] = false;
        return res;
    }

    public static void main(String[] args) {
        char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };
        String word = "ABCCED";
        System.out.println(new Solution().exist(board, word));
    }
}
